1. Technical Field
Embodiments of the invention relate to the field of packet ordering, and more specifically to maintaining partial order of packets in packet processing modules.
2. Background Information and Description of Related Art
There are various processing functions that are applied to a packet as it passes through a router. A constraint for some of these processing functions is that they must process packets within a particular flow in the order they arrived at the router. At the same time, some processing functions do not have this requirement. In a system that has modules that require order processing and modules that do not require order processing, it becomes difficult to determine which packets to wait for.
In the context of network processors, the problem of mapping an arbitrary data-flow graph with a mix of in-order and out-of-order processing requirements is especially difficult because the network processor architecture involves a distributed, multiprocessing environment. For example, nodes of a router or switch's data flow graph get mapped on multiple processing engines, where each engine implements multiple hardware threads with non-preemptive scheduling. In such a design, packets from the same flow may not be handled by the same thread. Thus, packets could arrive at modules out of order.